Permutation Matrix
Definition
A permutation matrix is a square matrix containing exactly one entry of \(1\) on each row and on each column, and \(0\) elsewhere.
The idea of a permutation matrix is to describe a permutation of the elements of the vector the matrix is applied to. For example
\[ \begin{bmatrix}
a \\ b \\ c \\ d \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
\end{bmatrix}
=
\begin{bmatrix}
a \\ d \\ b \\ c \\
\end{bmatrix}.\]
That is, if \((m)_{i, j} = 1\), then the \(j^{\text{th}}\) element of the output vector is equal to the \(i^{\text{th}}\) element of the input vector upon multiplication by \(M\).
One element of \(1\) in each row guarantees selecting only one element in the output, and one element of \(1\) in each column guarantees that element in the input vector appears only once in the output.